package com.mzy.linear_struct.subject;

import java.util.function.Predicate;

/**
 * @Author: codermzy
 * @Date: 2024/04/28/下午1:44
 * @Description:
 */
public class 买卖股票的最佳时机121 {

    static class Solution {
        public int maxProfit(int[] prices) {
            int n = prices.length;
            // 1. 定义状态
            int[] dp = new int[n];

            // 2. 定义状态转移方程
            // dp[n] = Math.max(dp[n-1], dp[n] - minValue)

            // 3. 定义状态
            dp[0] = 0;
            int minValue = prices[0];
            for (int i = 1; i < prices.length; i++) {
                // 4. 计算结果
                minValue = minValue < prices[i] ? minValue : prices[i];
                dp[i] = Math.max(dp[i - 1], prices[i] - minValue);
            }

            return dp[n - 1];
        }
    }





    public static void main(String[] args) {
        int[] arr = {7, 1, 5, 3, 6, 4};
        System.out.println(new Solution().maxProfit(arr));
    }
}
